Low-Density Parity-Check (LDPC) codes are a type of linear error-correcting codes that are part of the family of linear block codes, which transform a message consisting of a sequence of information symbols of an alphabet into a fixed length sequence of encoding symbols. With linear block codes the input message length is less than the number of encoding symbols thereby providing redundancy allowing for detection and correction of errors. LDPC codes were originally invented by Gallager, see “Low Density Parity-Check Codes” (Monograph, M.I.T. Press, 1963), but little attention was devoted to them at the time, primarily because the required decoding complexity was too high for the processing resources that were available. In 1993, the introduction of turbo codes by Berrou, Glavieux and Thitimajshima, see “Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes” (Proc. IEEE Intl. Comm. Conf., pp 1064-1070, 1993), spurred interest for codes that could achieve error correction at rates approaching the channel capacity of the link they were applied upon. In the intervening 30 years semiconductor devices had gone from expensive Small Scale Integrated Circuits with tens to hundreds of transistors to consumer electronics such as Intel's fifth-generation microarchitecture, the P5 or Pentium, with 3 million transistors. LDPC codes were rediscovered by MacKay in the mid-1990s, see D. J. C. MacKay et al in “Near Shannon Limit Performance of Low Density Parity Check Codes” (Electronics Letters, vol. 32, pp. 1645-1646, August 1996).
LDPC codes are interesting mainly for two reasons. First, they offer an error correction performance that approaches the channel capacity exponentially fast in terms of the code length. Secondly, the decoding process has linear complexity and a high degree of parallelism that scales with the code length. LDPC codes are capacity approaching codes, meaning that practical constructions exist that allow transmitting information at a signal-to-noise ratio that is very close to the theoretical minimum, known as the Shannon limit. Using iterative belief propagation techniques, LDPC codes can be decoded in time linearly to their block length, a factor particularly beneficial as data rates in communication systems continue to increase.
LDPC codes, therefore, are finding increasing use in applications where reliable and highly efficient information transfer is desired. Although implementation of LDPC codes has lagged that of other codes, notably turbo codes, they are increasingly becoming the standard for error-correction in many applications including, but not limited to:                Digital Video Broadcasting-Satellite-Second Generation (DVB-S2) standard;        Forward Error Correction (FEC) within the ITU-T G.hn home network standard providing data rates up to 1 Gb/s over power lines, phone lines and coaxial cables;        IEEE 802.16e WiMAX;        IEEE 802.16n WiFi; and        IEEE 802.3an (10GBase-T Ethernet on CAT6 cables, which operates at 10 Gb/s).        
Of significant importance for such applications, which address high-speed applications in essentially consumer markets, is the ability to implement economically and technically viable decoder circuits, since typically the implementation of the encoder is much less complex. By viable we mean one where the circuits have small die area, and hence low manufacturing cost, efficient power performance, and good processing performance in terms of throughput and latency, yet preserves the error-correction capability of the code.
The design of practical decoding algorithms does not focus so much on the coding gain offered by one code compared to another, but rather on the performance of a given algorithm on a given code. The aim is to optimize error-correction performance versus cost on the widest possible range of codes. Accordingly, throughout the following specification where cost is assessed it is done so at the algorithm level and hence in general terms.
At present amongst the challenges related to the decoding of LDPC codes are the decoding complexity of binary error-correction codes themselves and error floors. Decoding complexity for example means that today the codes chosen for IEEE 802.16e WiMAX and IEEE 802.3an Ethernet standards perform roughly 3 dB away from capacity, in part due to the cost of decoding circuits. Accordingly, reducing decoder cost using improved algorithms therefore permits increased efficiency of channel use in such applications. The phenomenon of error floors refers to the fact that LDPC codes can loose error-correction efficiency when the target error rate is very low. This problem is sometimes studied at the level of the code design, but given that the behavior is influenced by the choice of decoding algorithm and by implementation constraints, it is also possible to address this issue at the algorithm level.
Min-Sum Decoder:
Amongst the best known decoding algorithms for decoding LDPC codes is the Min-Sum algorithm (MS). Whilst the MS algorithm has decoding performance that is inferior to the Sum-Product algorithm (SP), the offset MS algorithm, which is a version of the MS algorithm, works very close to the performance achieved using SP algorithm. It has been shown in the prior art that a relaxed version of the MS algorithm has the potential to surpass the decoding performance of SP decoders, see S. Hemati et al in ““Dynamics and Performance Analysis of Analog Iterative Decoding for Low-Density Parity-Check (LDPC) Codes,” (IEEE Trans. Comm. Vol. 54, pp. 61-70). It would therefore be beneficial to implement variants of the MS algorithm with low complexity and low power. Accordingly, the inventors have established a simple low-power and low-cost digital MS decoder that can be implemented with very simple and small processing nodes. This MS decoder also manages the power consumption in the wiring interconnecting the processing nodes which is a common problem in iterative decoders. The novel MS decoder exploits the fact that in a log-likelihood ratio (LLR) domain, the operations of an MS decoder become very simple. Accordingly, the digital MS decoder according to embodiments of the invention has variable nodes where the only operation is addition and check nodes where we have to only find the minimum absolute value of the incoming messages and XOR their sign bits. In the novel MS decoder the channel outputs are used directly and there is no requirement for an estimation of the noise power in MS decoders according to embodiments of the invention.
Delayed Stochastic Decoder:
In stochastic decoding information is represented by a data stream (either binary or non-binary) which represents numbers by a weighted stream of bits with binary digits inserted at random intervals such that the weight of one's or zeros' represents the number value. In the stochastic bit stream, complex mathematical operations are simplified to bitwise operations which can be performed by small logic functions. Within the prior art it has been shown that the performance of the stochastic decoders can exceed that of the current state of the art SP decoders.
In conventional LDPC decoders the logical hardware required to perform the computation is very large, and so the system is typically reduced by implementing a small subset of the required hardware and re-using it to perform a subset of the computations. This is known as the partially parallel architecture and results in several subsets of the computation being performed in series by progressing from one set of data to the next, and storing the intermediate results until the entire computation is completed. Whilst reducing logical hardware complexity the approach requires an additional memory (storage) overhead, increases power consumption, and incurs a delay in processing. Further when the length of a block code increases, the fully parallel implementation of the decoders is not trivial task, even using current stochastic methods. It would therefore be beneficial to be able to implement Stochastic Decoding in an architecture with reduced memory, reduced latency, and reduced power consumption. Accordingly, the inventors have established a method of implementing digital stochastic decoders that are simple, operate at low power, and can be implemented with low cost though the use of small and efficient processing nodes using a technique the inventors call “Delayed Stochastic” decoding.
Re-Decoding:
Beyond the actual physical implementation of decoders such as MS decoders, SP decoders etc. it is important to also assess the error rate performance of error correction codes such as a LDPC code and the different decoder implementations. In doing so it is common to discuss the error floor, an error floor being the region where there is diminishing return in the error-rate versus signal to noise ratio (SNR) as the SNR increases. Error rate being an important aspect of digital communications as high error rates require storage of the data at transmitting nodes, re-transmission, delays, increased network overhead etc. in respect of providing the content to the user associated with the digital data. This error floor is determined by a combination of the structure of the specific code employed as well as the decoding algorithm used to decode the encoded data. Error floors further constitute a significant limitation for communication systems when the desired error rate is below the error floor of the encoding/decoding system.
Error floors typically arise from the existence of weak sub-graph topologies within the code graph that are caused by the specific configuration of cycles in the graph. The term trapping sets is widely used to describe these sub-graphs. A received bit is said to be eventually correct if there exists an I such that the bit is correct for all subsequent iterations, namely i>I. A trapping set is defined as a set of received bits that are not eventually correct and that, together with their neighboring check nodes, form a connected sub-graph. The fact that the bits are not eventually correct implies that the decoder is not making progress, either because it has reached a stable point end point, or because it is oscillating, in which case the combination of oscillating states can also be defined as a stable point.
Valid codewords are also stable end points, and for this reason invalid stable points are commonly referred to as pseudo-codewords. The sub-graph of a trapping set is composed of the variable nodes that are not eventually correct, plus all the neighboring check nodes. Since the check nodes compute a parity-check equation, those having an even degree with respect to the sub-graph will be satisfied, and those having an odd degree will be unsatisfied. An (a,b) trapping set is defined as having a variable nodes and b odd degree check nodes with respect to the sub-graph. The set of variable nodes involved in the trapping set is denoted D, O(D), and E(D) are the sets of check nodes adjacent to D that have respectively odd and even degrees with respect to D. The neighborhood set N(D) is the set of all variable nodes adjacent to check nodes in O(D), with the implication that D is a proper subset of N(D).
The probability of a decoding error is lower bounded by the probability that some erroneous received bits form a trapping set of the code. If we assume a memory-less channel, this probability is a function of the a-priori bit error rate, which decays much slower than the coded error rate for typical signal-to-noise ratios that are of interest in typical communication systems. However, with additive white Gaussian noise (AWGN) on the channel there is no simple relationship between the received values and convergence of the decoder to a pseudo-codeword which produces a decoding failure. As a result, trapping sets can be viewed as structures that reinforce existing errors on a group of bits. If the errors in the set are not too strong while the values in N(D)\D are very reliable, it is possible that some bits in the set are corrected before the incorrect messages become too strong and accordingly convergence to the pseudo-codeword is avoided. Furthermore, the decoding trajectory can be affected by errors outside the trapping set, for example by making a check node in E(D) unsatisfied.
The trajectory of a decoder is defined as the sequence of states that it traverses until it terminates. The state space can be generalized for all algorithms as the space of all n(d+1) variable node inputs. Depending upon the decoder and the random choices made by a given decoder, several possible trajectories exist that go from a given initial state to a final stable state, whether this final state forms a codeword or a pseudo-codeword. Convergence to a pseudo-codeword depends on two competing characteristics of trapping sets: the amplification of the set-intrinsic information caused by positive feedback loops and the extrinsic information flow into the set. As iterative decoding progresses these trapping set errors become harder to correct.
Several deterministic approaches have been proposed in the prior art to resolve decoding failures caused by trapping sets. These solutions have a common basis in that they perform the decoding in two phases. The first phase uses a standard belief propagation decoder and if the decoding is successful after the first phase, the algorithm terminates. Otherwise, the decoder enters the second post-processing phase that has been designed to handle the trapping sets for that particular algorithm or algorithms. Optionally, the syndrome weight, the number of unsatisfied check nodes can be used to determine whether the failure was caused by a trapping set, and to decide whether to activate the second phase. This is based on the heuristic notion that if a received frame is too noisy to be decoded successfully, it is unlikely that the decoder will make much progress leading to a large number of unsatisfied check nodes, while if a frame was received with a manageable error, only a convergence to a pseudo-codeword could cause some parity-checks to remain unsatisfied after many iterations. Therefore, a relatively small number of unsatisfied checks remaining after the first phase are indicative of convergence to a pseudo-codeword.
Accordingly, considering trapping sets in LDPC codes for example, there exists a method to detect convergence to a non-global minimum, and it is understood how a local minimum state (pseudo-codeword) relates to the global minimum (codewords). Consequently several deterministic decoders have been devised to move the decoder out of a pseudo-codeword state in the second post-processing phase or as an extension of the first phase. However, all these decoders in order to operate with first and second phases require some knowledge of the trapping set structure. Accordingly, it would be beneficial to have a method to trigger moving a decoder between such phases that does not require knowledge of the trapping set structure. The inventors have established a method, termed re-decoding, that achieves this and hence does not depend upon such prior knowledge of the trapping sets, and in that sense the method may be applied fore generally to decoders.
Multi-Phase Decoding:
As noted supra iterative algorithms are employed in decoding, such as the aforementioned Min-Sum (MS) algorithm. Collectively the MS algorithm and similar iterative message passing algorithms that are also often used, such as the Sum-Product algorithm, are referred to as belief propagation (BP) algorithms. Convergence of BP algorithms to pseudo-codewords is related to the local processing of information at each node of the Tanner graph, and hence pseudo-codewords exist for all BP algorithms. Tanner graphs being bipartite graphs used to state constraints or equations which specify error correcting codes, where such codes are often used to construct longer codes from smaller ones and hence are employed in both encoders and decoders extensively.
This convergence to pseudo-codeword points as discussed above may be viewed as being responsible for error floors, and hence a lower bound on the achievable error rate of the BP decoding algorithm which is problematic for many applications. It is highly desirable in many applications to address this sub-optimality of BP decoders in the error floor region. Several algorithms have been proposed to reduce the number of decoding failures of BP algorithms and hence lower the error floor. To the best of the inventor's knowledge, these prior art solutions are based upon identifying the set of check nodes that remain unsatisfied in the case of a decoding failure. It would be beneficial therefore to have a methodology, and devices derived from said methodology, that reduces the number of decoding failures and produces a lower error floor without requiring identification of the check nodes explicitly and hence applicable to general BP decoders.
Accordingly, the inventors have established a methodology to achieve these goals with a reduced hardware complexity by providing multi-phase decoding. Received vectors that fail to be decoded by the standard decoding algorithm, the first phase, are forwarded to a second (and potentially further phases) wherein they are attempted again with the present invention. This second phase is independent from the first phase, unlike the prior art techniques, and exploits a random component for the decoding attempt(s) in the second phase. Further, as the second phase is independent of the first phase it can optionally be replicated to provide multiple independent decoding attempts or trials for received vectors that fail the first attempt thereby improving the overall success rate of the multi-phase decoder at decoding received vectors . . . .
Accordingly, the embodiments of the inventions described within the specification address the issues of decoding complexity in high-speed communication systems, thereby allowing reduced cost for implemented decoder circuits, and error floor reduction, thereby allowing improved link performance.